package 算法题;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * Created by Administrator on 2017/8/13.
 */
public class 打印字符串的所有排列 {
    public static void main(String[] args) {
        String str="abc";
        ArrayList<String> strings = sortString(str);
        System.out.println(strings.toString());
    }
    public  static ArrayList<String> sortString(String str) {
        ArrayList<String> result = new ArrayList<String>() ;
        if(str==null || str.length()==0) { return result ; }

        char[] chars = str.toCharArray() ;
        TreeSet<String> temp = new TreeSet<>() ; //因为二叉树对于字符串默认按照字典顺序排列(还有Collections.sort()也是)
        sort(chars, 0, temp);
        result.addAll(temp) ; //将结果集添加到ArrayList集合中
        return result ;
    }

    public static void sort(char[] chars, int begin, TreeSet<String> result) {
        if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1) { return ; }

        if(begin == chars.length-1) { //解空间的第一个叶节点
            result.add(String.valueOf(chars)) ;  //找到一个解
        }else {
            for(int i=begin ; i<=chars.length-1 ; i++) {
                swap(chars, begin, i) ;//先begin和i交换位置

                sort(chars, begin+1, result);

                swap(chars, begin, i) ;//再把begin和i位置复原，即另一种情况（原始）
            }
        }
    }

    public static void swap(char[] x, int a, int b) {
        char t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}
